//
// Created by DELL on 2024/6/18.
//
#include "list_tool.h"

// 分成两部分反转，如果单数则中间节点不变
// 例如 [1, 2, 3, 4] -> [2, 1, 4, 3]
// 例如 [1, 2, 3, 4, 5] -> [2, 1, 3, 5, 4]


Node* reverseList(Node* head)
{
    if (head == nullptr || head->next == nullptr)
    {
        return head;
    }

    Node* fast = head;
    Node* slow = head;
    Node* secondHead = head;

    head = nullptr;
    while (fast != nullptr && fast->next != nullptr)
    {
        auto temp = slow;
        slow = slow->next;
        fast = fast->next->next;

        temp->next = head;
        head = temp;
    }

    if (fast != nullptr && slow != nullptr)
    {
        secondHead->next = slow;
        secondHead = slow;
        slow = slow->next;
        secondHead->next = nullptr;
    }

    while (slow != nullptr)
    {
        auto temp = slow;
        slow = slow->next;
        temp->next = secondHead->next;
        secondHead->next = temp;
    }

    return head;
}

int main()
{
    std::vector<int> nums{1, 2, 3, 4, 5, 6, 7};

    auto head = createList(nums);
    printList("list: ", head);

    head = reverseList(head);
    printList("Reverse List: ", head);


    return 0;
}
